﻿#include <iostream>
#include <vector>

using namespace std;

#define ONE 1
#define ZERO 0

static vector<int> linesForMostOne(int* matrix, int rowSize, int colSize)
{
    int x = colSize - 1;
    int y = 0;
    int maxOneCount = 0;
    int curOneCount = 0;
    vector<int> lines;
    while (x >= 0 && y < rowSize)
    {
        int cur = matrix[x + y * colSize];
        if (cur == ONE)
        {
            if (x >= 1 && matrix[x - 1 + y * colSize] == ONE)
            {
                --x;
            }
            else
            {
                curOneCount = colSize - x;
                if (curOneCount > maxOneCount)
                {
                    maxOneCount = curOneCount;
                    lines.clear();
                    lines.push_back(y);
                }
                else if (curOneCount == maxOneCount)
                {
                    lines.push_back(y);
                }

                curOneCount = 0;
                ++y;
            }
        }
        else
        {
            curOneCount = 0;
            ++y;
        }
    }

    return lines;
}

/**
 * 一个二维数组中，每一行由0和1组成，0一定在每一行的左侧，1在右侧。有可能一行全是0，也有可能一行全是1.
 * 求1数量最多的是哪几行？
 *
 * 例如:
 *    0 0 0 0 0 0 1 1
 *    0 0 0 1 1 1 1 1
 *    0 0 0 0 1 1 1 1
 *    0 0 0 0 0 0 0 1
 *    0 0 0 0 0 0 0 0
 *    0 1 1 1 1 1 1 1
 *
 * 第5行即为所求。
 *
 * 思路：
 * 从右上角开始搜索
 * 1. 向左走，到达最左侧的1，记录1的个数
 * 2. 向下走，如果是0，继续向下；如果是1，则向左走
 * 3. 重复步骤1, 直到走到最后一行
 */
int main_OneLineWithMostOne()
{
    int colSize = 8;
    int matrix[] = {
        0,0,0,0,0,0,1,1,
        0,1,1,1,1,1,1,1,
        0,0,0,0,1,1,1,1,
        0,0,0,0,0,0,0,1,
        0,0,0,0,0,0,0,0,
        0,1,1,1,1,1,1,1,
    };

    int rowSize = sizeof(matrix) / (sizeof(int) * colSize);
    auto lines = linesForMostOne(matrix, rowSize, colSize);
    for (auto it = lines.begin(); it != lines.end(); ++it)
    {
        printf("%d\n", *it);
    }

    return 0;
}